In a computer system, a memory is usually formed from a plurality of dynamic random access memory (DRAM) chips. DRAMs are generally organized into square arrays. For example, a conventional 256K DRAM has 512 rows and 512 columns, while a conventional 1M DRAM has 1,024 rows and 1,024 columns.
DRAMs have row select lines and column select lines. A DRAM is operated by first selecting a row and then selecting a column. It is a characteristic of conventional DRAMs that prior to selecting a row, the row select line must be pre-charged. If one seeks to access locations which are on different rows, after the first operation, one must wait for the row select line to be pre-charged before one can execute another operation.
However, it is not necessary to pre-charge the column select line before selecting a column. Thus, the amount of time to select a column is considerably less than the amount of time required to select a row. It is possible to execute a relatively slow row select operation and then to quickly select a number of columns from that row. The type of operation wherein a slow row select is followed by several fast column selects is generally referred to as a page mode operation of a DRAM. In the page mode, one can select words within a page much faster than one can select words which are on different pages. Thus, the page mode is one technique which can be utilized to improve DRAM performance.
Another technique which can be utilized to improve DRAM performance involves the use of interleaved memory banks. According to this technique, memory is divided into two or more separate memory banks. Sequential memory locations are stored in sequential memory banks. For example, memory may be divided into two memory banks referred to as "even" and "odd." Sequential memory locations are stored alternately in the even and the odd memory banks. If there is an instruction to read from two sequential memory locations, the first location is read from the first, e.g., the even, memory bank, and, while that bank is being pre-charged, the second location is read from the second, e.g., the odd, memory bank. Thus, because sequential locations will be stored in different memory banks, they can be read very quickly without waiting for an intervening pre-charge cycle.
In U.S. Pat. No. 4,924,375 (Fung et al.), a memory access system is disclosed which combines both page mode operation and interleaved memory in order to achieve high performance. According to this patent, memory is organized into one, two, or four memory banks. Furthermore, each of the memory banks is divided into pages each of which comprises a single row with 2K columns per row. Sequential pages are interleaved among the memory banks so that memory accesses which are a page apart will be to two different memory banks. Sequential accesses to locations on the same page omit the pre-charge cycle, thus speeding up the memory cycle. Sequential accesses to separate memory banks are likewise speeded up since there is no need to wait for the completion of a pre-charging cycle before initiating the next access.
Thus, the memory system disclosed in U.S. Pat. No. 4,924,375 employs both page mode and interleaved memory in order to improve performance of the computer. However, this known memory system has certain limitations. In particular, the memory system disclosed in U.S. Pat. No. 4,924,375 has only four memory banks. It is not easily adaptable to a computer having an arbitrary number of memory banks. Furthermore, this known memory system is only suitable for use in a computer having a single master or microprocessor. If used in conjunction with a computer having multiple masters, additional bank-conflict states may be introduced in the event two masters attempt to access the same memory bank at the same time. There is no disclosure in U.S. Pat. No. 4,924,375 for resolving such bank-conflict states.
Accordingly, it is an object of the present invention to provide a memory access system which is suitable for use in a computer having a plurality of memory banks and a plurality of masters, for example, microprocessors.
It is a further object of the invention to provide a memory access system suitable for use in a computer having M (M&gt;1) memory banks and N (N&gt;1) masters, which memory access system employs page mode and interleaved memory for enhancing performance.
It is yet another object of the present invention to provide a memory access system suitable for use in a computer having M memory banks and N masters, which memory access system provides means for resolving bank-conflict states when several masters simultaneously request access to the same memory bank.
It is yet another object of the present invention to provide a memory access system for use in a computer having M memory banks and N masters which memory access system ensures that requests for access to memory by a particular master are satisfied in First-In-First-Out order.